//
// Created by 123 on 2024/3/10.
//
#include <iostream>

using namespace std;

void get_next(string s, int next[]);

int kmp(string s1,int next[],string s2);

void show(int a[],int len);
int main() {
    string s1="abcadabcalabcaca";
    string s2 = "abcac";
    int next[s2.length()];
    get_next(s2,next);
    show(next,s2.length());
    cout<<kmp(s1,next,s2)<<"   <----------"<<endl;



}



void show(int a[],int len){
    for (int i = 0; i < len; ++i) {
        cout<<a[i]<<"   ";
    }
    cout<<endl;
}

int kmp(string s1,int next[],string s2){
    if(s2.length()>s1.length()||s1.length()==0)
        return -1;
    int i=0;
    int j=0;
    while(i<s1.length()&&j<s2.length()){
        if(s1[i]==s2[j]){
            i++;
            j++;
        }else if(next[j]==-1){
            i++;
        }else{
            j=next[j];
        }
    }
    return j==s2.length()?i-j:-1;
}

void get_next(string str, int next[]) {
    next[0] = -1;
    next[1] = 0;
    int i = 2;
    int cn = 0;
    while (i < str.length()) {
        if (str[i-1] == str[cn]) {
            next[i++] = ++cn;
        } else if (cn > 0) {
            cn = next[cn];
        }else{
            next[i++]=0;
        }
    }
}